import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] a = {76,56,12,34,78,90,13,5};
//        selectSort(a);
//        selectSort1(a);
        HeapSort(a);
        System.out.println(Arrays.toString(a));
        int[] a1 = {76,56,12,34,78,90,13,5};
        Arrays.sort(a1);

        System.out.println(Arrays.toString(a1));
    }
    //时间复杂度O(nlogn)
    //空间复杂度O(1)
    //稳定性:不稳定
    private static void HeapSort(int[] a) {
        GreateBigHeap(a);//O(n)
        int end = a.length -1;
        //O(nlogn)
        while (end > 0){
            swap(a,0,end);
            shifDown(a,0,end);
            end--;
        }
    }

    private static void GreateBigHeap(int[] a) {
        for (int parent = (a.length-1-1)/2; parent >= 0 ; parent--) {
            shifDown(a,parent,a.length);

        }
    }

    private static void shifDown(int[] a, int parent, int length) {
        int child = 2 * parent +1;
        while (child < length){
            if(child +1 < length  && a[child+1] > a[child]){
                child++;
            }
            if(a[child] > a[parent]){
                swap(a,child,parent);
                parent = child;
                child = 2 * parent +1;
            }else {
                break;
            }
        }
    }

    //时间复杂度O(n^2)
    //空间复杂度O(1)
    //不稳定
    private static void selectSort1(int[] a) {
        int l = 0;
        int r = a.length - 1;
        while (l < r){
            int max = l;
            int min = l;
            for (int i = l + 1; i <= r; i++) {
                if(a[i] < a[min]){
                    min = i;
                }
                if(a[i] > a[max]){
                    max = i;
                }

            }
            swap(a,l,min);

            //如果max下标正好是left.则已经把最大值从left位置换的了min
            if(l == max){
                max = min;
            }
            swap(a,r,max);
            l++;
            r--;
        }
    }

    //时间复杂度:O(n^2)
    //和数据是否有序是否无关
    //空间复杂度:O(1)
    private static void selectSort(int[] a) {
        for (int i = 0; i < a.length; i++) {
            int minindex = i;
            for (int j = i+1; j < a.length ; j++) {
                if(a[j] < a[minindex]){
                    minindex = j;
                }
            }
            if(minindex != i){
                swap(a,i,minindex);
            }
        }
    }

    private static void swap(int[] a, int i, int minindex) {
        int tmp = a[i];
        a[i] = a[minindex];
        a[minindex] = tmp;
    }
}
